class Solution
{
public:
    int minGroupsForValidAssignment(vector<int> &nums)
    {
        unordered_map<int, int> count;
        for (auto num : nums)
        {
            count[num]++;
        }

        vector<int> counts;
        for (auto [_, c] : count)
        {
            counts.push_back(c);
        }

        sort(counts.begin(), counts.end());

        int minGroups = INT_MAX;
        for (int groupSize = counts[0] + 1; groupSize >= 1; --groupSize)
        {
            int groups = 0;
            bool valid = true;
            for (int c : counts)
            {
                int m = c % groupSize;
                int b = m == 0 ? m : groupSize - m;
                if ((c + b) / groupSize >= b)
                {
                    groups += (c + b) / groupSize;
                }
                else
                {
                    valid = false;
                    break;
                }
            }
            if (valid)
            {
                minGroups = min(minGroups, groups);
            }
        }
        return minGroups;
    }
};